package array

import "math"

func coinChange(coins []int, amount int) int {

	dp := make([]int, amount+1)
	for i := 1; i <= amount; i++ {
		dp[i] = math.MaxInt64 - 1
	}

	for _, coin := range coins {
		for i := range dp {

			if i == coin {
				dp[i] = 1
				continue
			}

			if i-coin > 0 && dp[i-coin] != math.MaxInt64-1 {
				dp[i] = min(dp[i], dp[i-coin]+1)
			}
		}
	}

	if dp[amount] == math.MaxInt64-1 {
		return -1
	}
	return dp[amount]

}
